package com.jxb.dp20251355;

import java.util.Arrays;

public class LongestIncrSubseq_300 {

    public static void main(String[] args) {

    }

    /*标准DP实现*/
    //dp[i]属于最长子序列
    //实现逻辑
    //经过2次遍历
    //  第一层遍历，遍历原数组的值
    //  第二层遍历，遍历第一层i元素之前的值做比较，若大于，将长度加1赋值给当前i位置的dp数组中
    public int lengthOfLIS(int[] nums) {
        //定义dp数组，dp[i]，第i位元素子序列的长度
        int[] dp = new int[nums.length];
        //dp数组初始化
        Arrays.fill(dp,1);
        //遍历原数组，对dp数组进行填充
        // * 输入：nums = [10,9,2,5,3,7,101,18]
        //  * 输出：4
        //dp[3] = 2
        //dp[4] = 3
        //dp[5] = 4
        for (int i = 0;i<nums.length;i++) {
            for (int j = 0;j<i;j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //遍历dp数组，找出最大值
        int res = 0;
        for (int i = 0;i<dp.length;i++) {
            res = Math.max(res,dp[i]);
        }
        return res;
    }

    /*二分查找+DP实现*/
    //重新定义dp数组
    //dp数组存放当前遍历的元素值，每次存放时，会去判断与dp数组最后一个元素的大小比较
    //  若大于最后一个元素，放在最后一个元素的后面
    //  若小于最后一个元素，通过二分查找法，找出比他小的或者相等的元素，替换它
    public int lengthOfLIS3(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        //初始化dp数组
        int result = 1;
        dp[0] = nums[0];
        for (int i = 1;i<length;i++) {
            if (nums[i] > dp[result - 1]) {
                dp[result] = nums[i];
                result++;
            }else {
                int start = 0,end = result;
                while (start < end) {
                    int m = (start + end) / 2;
                    if (dp[m] < nums[i]) {
                        start = m + 1;
                    }else {
                        end = m;
                    }
                }
                dp[start] = nums[i];
            }
        }
        return result;
    }

}
